{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If Array Pairs Are Divisible by k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canArrange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查数组对是否可以被 k 整除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 和一个整数 <code>k</code> ，其中数组长度是偶数，值为 <code>n</code> 。</p>\n",
    "\n",
    "<p>现在需要把数组恰好分成 <code>n /&nbsp;2</code> 对，以使每对数字的和都能够被 <code>k</code> 整除。</p>\n",
    "\n",
    "<p>如果存在这样的分法，请返回 <em>True</em> ；否则，返回 <em>False</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4,5,10,6,7,8,9], k = 5\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4,5,6], k = 7\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4,5,6], k = 10\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n</code> 为偶数<meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-array-pairs-are-divisible-by-k](https://leetcode.cn/problems/check-if-array-pairs-are-divisible-by-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-array-pairs-are-divisible-by-k](https://leetcode.cn/problems/check-if-array-pairs-are-divisible-by-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,10,6,7,8,9]\\n5', '[1,2,3,4,5,6]\\n7', '[1,2,3,4,5,6]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        counts=[0]*k\n",
    "        for num in arr:\n",
    "            counts[num%k]+=1\n",
    "        l,r=1,k-1\n",
    "        while l<r:\n",
    "            if counts[l]!=counts[r]:\n",
    "                return False\n",
    "            l+=1\n",
    "            r-=1\n",
    "        if l==r and counts[l]%2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = [0] * k\n",
    "        for x in arr:\n",
    "            cnt[x % k] += 1\n",
    "        \n",
    "        for i in range(1, k // 2 + 1):\n",
    "            if cnt[i] != cnt[k - i]:\n",
    "                return False\n",
    "        return cnt[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = [0] * k\n",
    "        for x in arr:\n",
    "            cnt[x % k] += 1\n",
    "        \n",
    "        for i in range(1, k // 2 + 1):\n",
    "            if cnt[i] != cnt[k - i]:\n",
    "                return False\n",
    "        return cnt[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        hp = [0]*k\n",
    "        for num in arr:\n",
    "            num = num%k\n",
    "            rem = (k-num)%k\n",
    "            if hp[rem]>0:\n",
    "                hp[rem]-=1\n",
    "                hp[num]-=1\n",
    "            hp[num]+=1\n",
    "        return sum(hp)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canArrange(self,arr, k):\n",
    "        remainders = [0] * k # 余数数组，存储的是arr中每一个数除以k所得余数为remainders[i]的次数\n",
    "        for a in arr:\n",
    "            remainders[a%k] += 1\n",
    "        if remainders[0] % 2 != 0: # 如果余数为0的次数是奇数，鉴于arr一共有偶数个数字，所以余数不为0的次数就是奇数，无法达成题意\n",
    "            return False\n",
    "        for i in range(1, int(k/2)+1):\n",
    "            if remainders[i] != remainders[k-i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = [0] * k\n",
    "        for x in arr:\n",
    "            cnt[x % k] += 1\n",
    "        for i in range(1, k // 2 + 1):\n",
    "            if cnt[i] != cnt[k - i]:\n",
    "                return False\n",
    "        return cnt[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for num in arr:\n",
    "            mod[num % k] += 1\n",
    "        if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1)):\n",
    "            return False\n",
    "        return mod[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for v in arr:\n",
    "            mod[v % k] += 1\n",
    "        for i in range(1, k // 2 + 1):\n",
    "            if mod[i] != mod[k - i]:\n",
    "                return False\n",
    "        if mod[0] % 2 == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = [0] * k\n",
    "        for i in range(len(arr)):\n",
    "            cnt[arr[i] % k] += 1\n",
    "        if cnt[0] % 2 != 0:\n",
    "            return False\n",
    "        for i in range(1,k//2+1):\n",
    "            if cnt[i] != cnt[k-i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        \n",
    "        rec = [0]*k \n",
    "\n",
    "        for num in arr:\n",
    "            rec[num%k] = rec[num%k] + 1\n",
    "\n",
    "        if(rec[0]%2!=0):\n",
    "            return False\n",
    "\n",
    "        for i in range(1, k//2+1):\n",
    "            first = rec[i]\n",
    "            second = rec[k-i]\n",
    "            if(first!=second):\n",
    "                return False\n",
    "            \n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:# py3\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        freq = [0]*k\n",
    "        for a in arr:\n",
    "            freq[(a%k+k)%k] += 1\n",
    "        if freq[0]&1:\n",
    "            return False\n",
    "        for i in range(1, k//2+1):\n",
    "            if freq[i] != freq[k-i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = [0] * k\n",
    "        for x in arr:\n",
    "            cnt[x % k] += 1\n",
    "        for i in range(1, k // 2 + 1):\n",
    "            if cnt[i] != cnt[k - i]:\n",
    "                return False\n",
    "        return cnt[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for num in arr:\n",
    "            mod[num % k] += 1\n",
    "        if any(mod[i] != mod[k-i] for i in range(1, k//2 + 1)):\n",
    "            return False\n",
    "        return mod[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        modArr = [0] * k\n",
    "        for i in arr:\n",
    "            modArr[i%k] +=1\n",
    "        for index,j in enumerate(modArr):\n",
    "            if index==0:\n",
    "                if j%2 !=0:\n",
    "                    return False\n",
    "            elif modArr[index] != modArr[k-index]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        l = [0] * (k)\n",
    "        for a in arr:\n",
    "            m = a % k\n",
    "            l[m] = l[m] + 1\n",
    "        # print(l)\n",
    "        for i in range(k//2 + 1):\n",
    "            if i == 0 or i * 2 == k:\n",
    "                if l[i] % 2 == 1:\n",
    "                    return False\n",
    "            else:\n",
    "                if l[i] != l[k - i]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        #数组中的元素分别对K取余，存入新的数组tmp. 然后把 tmp 中的0取出来，若个数不为偶数，返回False. \n",
    "        #把tmp中的非0元素取出来，排序，收尾相加判断是否等于k。\n",
    "        tmp = []\n",
    "        s = 0\n",
    "        ss = []\n",
    "        for i in arr:\n",
    "            tmp.append(i % k)\n",
    "        for j in tmp:\n",
    "            if j == 0:\n",
    "                s += 1\n",
    "            else:\n",
    "                ss.append(j)\n",
    "        if s % 2 != 0:\n",
    "            return False\n",
    "        ss.sort()\n",
    "        m = len(ss)\n",
    "        for h in range(m):\n",
    "            if (ss[h] + ss[m-h-1]) != k:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            # arr.sort()\n",
    "            # lens = len(arr)\n",
    "            # a = lens // 2\n",
    "            # arra = arr[:a]\n",
    "            # arrb = arr[a:]\n",
    "            # count = 0\n",
    "            # for _ in range(len(arra)):\n",
    "            #     sa = arra[0]\n",
    "            #     for j in arrb:\n",
    "            #         ss = (j + sa) % k\n",
    "            #         if ss == 0:\n",
    "            #             arra.remove(arra[0])\n",
    "            #             arrb.remove(j)\n",
    "            # if arra == [] and arrb == []:\n",
    "            #     return True\n",
    "            # else:\n",
    "            #     return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for num in arr:\n",
    "            mod[num % k] += 1\n",
    "        if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1)):\n",
    "            return False\n",
    "        return mod[0] % 2 == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for num in arr:\n",
    "            mod[num % k] += 1\n",
    "        if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1)):\n",
    "            return False\n",
    "        return mod[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        a = [0]*k\n",
    "        for ar in arr:\n",
    "            s = ar % k\n",
    "            a[s] += 1\n",
    "        print(a)\n",
    "        if a[0] % 2 == 1:\n",
    "            return False\n",
    "        for i in range(1,k//2+1):\n",
    "            if a[i] != a[-i]:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = [0] * k\n",
    "        for num in arr:\n",
    "            mod[num % k] += 1\n",
    "        if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1)):\n",
    "            return False\n",
    "        return mod[0] % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        n = len(arr)\n",
    "        res = [0] * (k+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            res[arr[i]%k] += 1\n",
    "\n",
    "        print(res)\n",
    "        if k%2:\n",
    "            if res[0]%2:\n",
    "                return False\n",
    "            for i in range(1, k//2+1):\n",
    "                if res[i] != res[k-i]:\n",
    "                    return False\n",
    "        else:\n",
    "            if res[0]%2 or res[k//2]%2:\n",
    "                return False\n",
    "        for i in range(1, k//2):\n",
    "                if res[i] != res[k-i]:\n",
    "                    return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        non_zero = []\n",
    "        zero = []\n",
    "        for a in arr:\n",
    "            rest = a%k\n",
    "            if rest != 0:\n",
    "                non_zero.append(rest)\n",
    "            else:\n",
    "                zero.append(rest)\n",
    "        \n",
    "        if len(zero)%2 != 0:\n",
    "            return False\n",
    "        \n",
    "        non_zero.sort()\n",
    "        m = len(non_zero)\n",
    "        for i in range(m//2):\n",
    "            if non_zero[i] + non_zero[m-i-1] != k:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        nums=[]\n",
    "        zero_counter=0\n",
    "        for i in range(len(arr)):\n",
    "            n=arr[i]%k\n",
    "            if n==0:\n",
    "                zero_counter+=1\n",
    "            else:\n",
    "                nums.append(n)\n",
    "        if zero_counter%2==1:\n",
    "            return False\n",
    "        arr=nums\n",
    "        arr.sort()\n",
    "        for i in range(len(arr)//2):\n",
    "            if (arr[i]+arr[len(arr)-1-i])%k!=0:\n",
    "                return False\n",
    "\n",
    "        if len(arr)%2==1 and arr[len(arr)//2+1]%k!=0:\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        ls = [i%k for i in arr]\n",
    "        ls.sort(reverse = False)\n",
    "        zeros = ls.count(0)\n",
    "        if zeros % 2 != 0:\n",
    "            return False\n",
    "        ls = ls[zeros:]\n",
    "\n",
    "        n = len(ls)\n",
    "        print(ls)\n",
    "        for i in range(int(n / 2)):\n",
    "            if (ls[i] + ls[-i - 1]) % k != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        ls = [i%k for i in arr]\n",
    "        ls.sort(reverse = False)\n",
    "        zeros = ls.count(0)\n",
    "        if zeros % 2 != 0:\n",
    "            return False\n",
    "        ls = ls[zeros:]\n",
    "\n",
    "        n = len(ls)\n",
    "        print(ls)\n",
    "        for i in range(int(n / 2)):\n",
    "            if (ls[i] + ls[-i - 1]) % k != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        #先写个O(nlogn)，两数之和可以优化到O(n)\n",
    "        arr=[i%k for i in arr]\n",
    "        arr.sort()\n",
    "        i=0;j=len(arr)-1\n",
    "        while i<len(arr) and arr[i]==0:\n",
    "            i+=1\n",
    "        if i%2!=0:\n",
    "            return False\n",
    "        while i<j:\n",
    "            if arr[i]+arr[j]!=k:\n",
    "                return False\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        d = defaultdict(int)\n",
    "        for i in arr:\n",
    "            if (k - i) % k in d:\n",
    "                # 这一步其实 可以直接删除 （个人习惯）\n",
    "                d[(k - i) % k] -= 1\n",
    "                if d[(k - i) % k] == 0:\n",
    "                    del d[(k - i) % k]\n",
    "            else:\n",
    "                d[i % k]+=1\n",
    "        return d == {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(int)\n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = arr[i] % k\n",
    "            d[arr[i]] +=1\n",
    "        print(d)\n",
    "        if 0 in d:\n",
    "            if d[0]%2 ==0:\n",
    "                del d[0]\n",
    "            else:\n",
    "                return False\n",
    "        for i in d:\n",
    "            if d[i] != d[k-i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "      preNum = dict()\n",
    "\n",
    "      for num in arr:\n",
    "        target = (k - num % k) % k\n",
    "        if target in preNum:\n",
    "          preNum[target] -= 1\n",
    "          if preNum[target] == 0:  del preNum[target]\n",
    "        \n",
    "        else:\n",
    "          preNum[num % k] = preNum.get(num % k, 0) + 1\n",
    "      \n",
    "      return not preNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        n = len(arr)\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            tmp.append(arr[i]%k)\n",
    "        zero = [n for n in tmp if n ==0]\n",
    "        n_zero = [n for n in tmp if n!=0]\n",
    "        if len(zero)%2 != 0:return False\n",
    "        n_zero.sort()\n",
    "        m = len(n_zero)\n",
    "        for i in range(m):\n",
    "            if (n_zero[i]+n_zero[m-1-i]) != k:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        zeros = []\n",
    "        nzeros = []\n",
    "        for item in arr:\n",
    "            if (item + k) % k == 0:\n",
    "                zeros.append((item + k) % k)\n",
    "            else:\n",
    "                nzeros.append((item + k) % k)\n",
    "        print(nzeros)\n",
    "        nzeros.sort()\n",
    "        if len(zeros) % 2 != 0:\n",
    "            return False\n",
    "        \n",
    "        else:\n",
    "            for i in range(len(nzeros)//2):\n",
    "                if (nzeros[i] + nzeros[len(nzeros)-1-i]) % k != 0:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        n = len(arr)\n",
    "        if n % 2 != 0:\n",
    "            return False\n",
    "        if n == 0:\n",
    "            return False\n",
    "\n",
    "        for i in range(n):\n",
    "            arr[i] = arr[i] % k\n",
    "        dic = collections.Counter(arr)\n",
    "        if dic[0] % 2 != 0:\n",
    "            return False\n",
    "        if len(dic) == 1 and 0 not in dic.keys():\n",
    "            return False \n",
    "        for j in range(1,len(dic)):\n",
    "            \n",
    "            if dic[j] != dic[k - j]:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        first = []\n",
    "        second = []\n",
    "        flag = True\n",
    "        N = len(arr)\n",
    "        for i in range(N):\n",
    "            first.append(arr[i]%k)\n",
    "        zero = [n for n in first if n == 0]\n",
    "        nZero = [n for n in first if n != 0]\n",
    "        if len(zero) % 2 != 0:\n",
    "            return False\n",
    "        nZero.sort()\n",
    "        print(zero)\n",
    "        print(nZero)\n",
    "        M = len(nZero)\n",
    "        for i in range(M):\n",
    "            if (nZero[i] + nZero[M-1-i]) % k != 0:\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        ls = [i%k for i in arr]\n",
    "        ls.sort(reverse = False)\n",
    "        zeros = ls.count(0)\n",
    "        if zeros % 2 != 0:\n",
    "            return False\n",
    "        ls = ls[zeros:]\n",
    "\n",
    "        n = len(ls)\n",
    "        print(ls)\n",
    "        for i in range(int(n / 2)):\n",
    "            if (ls[i] + ls[-i - 1]) % k != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "      preNum = dict()\n",
    "\n",
    "      for num in arr:\n",
    "        target = (k - num % k) % k\n",
    "        if target in preNum:\n",
    "          preNum[target] -= 1\n",
    "          if preNum[target] == 0:  del preNum[target]\n",
    "        \n",
    "        else:\n",
    "          preNum[num % k] = preNum.get(num % k, 0) + 1\n",
    "      \n",
    "      return not preNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = arr[i] % k\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2 != 0:\n",
    "            return False\n",
    "        for i in range(1,k):\n",
    "            # if cnt[i] in cnt and cnt[k-i] in cnt:\n",
    "            if cnt[i] != cnt[k-i]:\n",
    "                # print(i,k-i)\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        n = len(arr)\n",
    "        _sum = sum(arr)\n",
    "        if _sum % k != 0:\n",
    "            return False\n",
    "        _map = dict()\n",
    "        for num in arr:\n",
    "            if num >= 0:\n",
    "                num = num % k\n",
    "            else:\n",
    "                t = -num % k\n",
    "                num = (k - t) % k\n",
    "            another = k - num\n",
    "            if another in _map:\n",
    "                _map[another] -= 1\n",
    "                if _map[another] == 0:\n",
    "                    _map.pop(another)\n",
    "            else:\n",
    "                if num not in _map:\n",
    "                    _map[num] = 1\n",
    "                else:\n",
    "                    _map[num] += 1\n",
    "        if 0 in _map:\n",
    "            _map.pop(0)\n",
    "        return len(_map) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "    r = {}\n",
    "    ret = 0\n",
    "    for n in arr:\n",
    "      m = n % k\n",
    "      mc = 0\n",
    "      if m != 0:\n",
    "        mc = r.get(k - m, 0)\n",
    "      else:\n",
    "        mc = r.get(m, 0)\n",
    "      if mc > 0:\n",
    "        ret += 1\n",
    "        if m != 0:\n",
    "          r[k - m] = mc - 1\n",
    "        else:\n",
    "          r[m] = mc - 1\n",
    "      else:\n",
    "        c = r.get(m, 0)\n",
    "        r[m] = c + 1\n",
    "    return ret == len(arr) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mapping  = {}\n",
    "        for a in arr:\n",
    "            if(a%k not in mapping):\n",
    "                mapping[a%k] = 1\n",
    "            else:\n",
    "                mapping[a%k] += 1\n",
    "        print(mapping)\n",
    "        for r in mapping:\n",
    "            if(r == 0):\n",
    "                if(mapping[r] % 2 == 1):\n",
    "                    return False\n",
    "            else:\n",
    "                if(k-r not in mapping or mapping[k-r] != mapping[r]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        n = len(arr)\n",
    "        dic = defaultdict(int)\n",
    "        for num in arr:\n",
    "            t = num % k\n",
    "            dic[t] += 1\n",
    "        print(dic)\n",
    "        for key, value in dic.items():\n",
    "            if key == 0 and dic[key] % 2 != 0:\n",
    "                return False\n",
    "            if key >0 and dic[key] != dic[k - key]:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        counter = defaultdict(int)\n",
    "        for num in arr:\n",
    "            counter[num % k] += 1\n",
    "        print(counter)\n",
    "        if counter[0] % 2 == 1:\n",
    "            return False\n",
    "        if counter[k / 2] % 2 == 1:\n",
    "            return False\n",
    "        for a in counter:\n",
    "            if a == 0:\n",
    "                continue\n",
    "            if counter[a] != counter[k - a]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = defaultdict(int)\n",
    "        for a in arr:\n",
    "            cnt[a % k] += 1\n",
    "        for key, value in cnt.items():\n",
    "            if key == 0 and cnt[key] % 2:\n",
    "                return False\n",
    "            if key != 0 and cnt[key] != cnt[k - key]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        arr = [i % k for i in arr]\n",
    "        c = Counter(arr)\n",
    "        for i in range(1, ceil(k / 2)):\n",
    "            if c[i] != c[k - i]:\n",
    "                return False\n",
    "        if k % 2 == 0 and c[k // 2] % 2 == 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        c = Counter([num % k for num in arr])\n",
    "        for i in range(1, (k + 1) // 2):\n",
    "            if c[i] != c[k - i]:\n",
    "                return False\n",
    "        # 只要继续判断余数为0的个数为偶数就可以\n",
    "        return True if c[0] % 2 == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        c = Counter([num % k for num in arr])\n",
    "        for i in range(1, (k + 1) // 2):\n",
    "            if c[i] != c[k - i]:\n",
    "                return False\n",
    "        return True if c[0] % 2 == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        # 使得每一对的和都能被k整除\n",
    "        # 按照其%k的模为k来找寻\n",
    "        hashmap = {}\n",
    "        for i in arr:\n",
    "            if i%k in hashmap:\n",
    "                hashmap[i%k] += 1\n",
    "            else:\n",
    "                hashmap[i%k] = 1\n",
    "        \n",
    "        if 0 in hashmap:\n",
    "            if hashmap[0] % 2 != 0:\n",
    "                return False\n",
    "        for i in hashmap.keys():\n",
    "            if i == 0:\n",
    "                continue \n",
    "            if k - i in hashmap:\n",
    "                if hashmap[k-i] != hashmap[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\r\n",
    "        cnt = Counter()\r\n",
    "        for x in arr:\r\n",
    "            cnt[x % k] += 1 \r\n",
    "        if cnt[0] & 1 or k & 1 == 0 and cnt[k // 2] & 1:\r\n",
    "            return False\r\n",
    "        for i in range(1, k // 2 + 1):\r\n",
    "            if cnt[i] != cnt[k - i]:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        arr = [i % k for i in arr]\n",
    "        c = Counter(arr)\n",
    "        # print(c, floor(k // 2))\n",
    "        for i in range(1, ceil(k / 2)):\n",
    "            if c[i] != c[k - i]:\n",
    "                return False\n",
    "        if k % 2 == 0 and c[k // 2] % 2 == 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        cnt = Counter(num % k for num in arr)\n",
    "        # 可以整除的数对\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in range(1, k):\n",
    "            # 取模不等的数对\n",
    "            if x != k - x and cnt[x] != cnt[k - x]:\n",
    "                return False\n",
    "            # 取模相等的数对\n",
    "            if x == k - x and cnt[x] % 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        d = dict()\n",
    "        for i in arr:\n",
    "            val = i % k\n",
    "            if val in d:\n",
    "                d[val] += 1\n",
    "            else:\n",
    "                d[val] = 1\n",
    "\n",
    "        if 0 in d and d[0] % 2 == 1:\n",
    "            return False\n",
    "\n",
    "        for i in range(1, k // 2 + 1):\n",
    "            a = 0\n",
    "            b = 0\n",
    "            if i in d:\n",
    "                a = d[i]\n",
    "            if k - i in d:\n",
    "                b = d[k - i]\n",
    "            if a != b:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        c = Counter([num % k for num in arr])\n",
    "        for i in range(1, (k + 1) // 2):\n",
    "            if c[i] != c[k - i]:\n",
    "                return False\n",
    "        # 只要继续判断余数为0的个数为偶数就可以\n",
    "        return True if c[0] % 2 == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        if sum(arr) % k != 0:\n",
    "            return False\n",
    "        hashmap = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            hashmap[(num % k)] += 1\n",
    "        print(hashmap)\n",
    "        for key in hashmap.keys():\n",
    "            if key == 0:\n",
    "                if hashmap[key] % 2 != 0:\n",
    "                    return False\n",
    "            else:\n",
    "                if hashmap[key] != hashmap[k - key]:\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        d = defaultdict(int)\n",
    "        for x in arr:\n",
    "            d[x%k]+=1\n",
    "        for key in d:\n",
    "            if key:\n",
    "                if d[k-key]!=d[key]:\n",
    "                    return False\n",
    "            else:\n",
    "                if d[key]%2!=0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            m = num % k\n",
    "            if m:\n",
    "                dic[m] += 1\n",
    "        for key,v in dic.items():\n",
    "            nk = k - key\n",
    "            if key == nk:\n",
    "                if v % 2:\n",
    "                    return False\n",
    "            elif nk not in dic or dic[nk] != v:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mapping  = {}\n",
    "        for a in arr:\n",
    "            if(a%k not in mapping):\n",
    "                mapping[a%k] = 1\n",
    "            else:\n",
    "                mapping[a%k] += 1\n",
    "        for r in mapping:\n",
    "            if(r == 0):\n",
    "                if(mapping[r] % 2 == 1):\n",
    "                    return False\n",
    "            else:\n",
    "                if(k-r not in mapping or mapping[k-r] != mapping[r]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        # 对arr数组按找余数取余，然后看余数加起来等于5的能否被组合玩\n",
    "        from collections import Counter\n",
    "        counter=Counter()\n",
    "        for x in arr:\n",
    "            counter[x%k]+=1\n",
    "        # print(counter)\n",
    "        for key in counter:\n",
    "            if key==0:continue\n",
    "            if counter[key]!=counter[k-key]:\n",
    "                return False \n",
    "        return True if counter[0]%2==0 else False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mapping  = {}\n",
    "        for a in arr:\n",
    "            if(a%k not in mapping):\n",
    "                mapping[a%k] = 1\n",
    "            else:\n",
    "                mapping[a%k] += 1\n",
    "        for r in mapping:\n",
    "            if(r == 0):\n",
    "                if(mapping[r] % 2 == 1):\n",
    "                    return False\n",
    "            else:\n",
    "                if(k-r not in mapping or mapping[k-r] != mapping[r]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        mod = collections.Counter(num % k for num in arr)\n",
    "        for t, occ in mod.items():\n",
    "            if t > 0 and (k - t not in mod or mod[k - t] != occ):\n",
    "                return False\n",
    "        return mod[0] % 2 == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canArrange(self, arr: List[int], k: int) -> bool:\n",
    "        remainder_dict = defaultdict(int)\n",
    "        total_num = 0\n",
    "        for num in arr:\n",
    "            remainder = num%k\n",
    "            target = k if remainder>0 else 0\n",
    "            if remainder_dict[target-remainder]>0:\n",
    "                remainder_dict[target-remainder]-=1\n",
    "                total_num-=1\n",
    "            elif remainder>0 and remainder_dict[-remainder]>0:\n",
    "                remainder_dict[-remainder]-=1\n",
    "                total_num-=1\n",
    "            else:\n",
    "                remainder_dict[remainder]+=1\n",
    "                total_num+=1\n",
    "            # print(num,remainder,remainder_dict)\n",
    "        return total_num==0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
